import java.util.*;

public class test2 {
    public static void main(String[] args) {
        ListNode A = new ListNode(1);
        ListNode B = new ListNode(2);
        ListNode C = new ListNode(2);
        ListNode D = new ListNode(1);

        A.next = B;
        B.next = C;
        C.next = D;

        System.out.println(isPalindrome(A));
        Map<Integer,Integer> map = new HashMap<>();
    }
    public static boolean isPalindrome(ListNode head) {
        // 让链表走到一半,其中前面一半都放入栈中,然后继续遍历出栈
        Stack<Integer> stack = new Stack<>();
        ListNode cur1 = head;
        int size = 0;
        while(cur1!=null){
            size++;
            cur1 = cur1.next;
        }

        // 计算中间数,开始遍历 要注意单数双数
        int mid = size/2; //如果是单数,这个值就是中间数的值-1
        ListNode cur2 = head;
        // 先遍历到中间,然后判定是否需要单数处理
        while(mid!=0){
            stack.push(cur2.val);
            cur2 = cur2.next;
            mid--;
        }
        if(size%2!=0) cur2 = cur2.next; // 代表是单数,中间位置不需要进行判定
        // 遍历栈
        while(!stack.isEmpty()&&cur2!=null){
            if(cur2.val!=stack.pop()) return false;
            cur2 = cur2.next;
        }
        return true;
    }
}
